using System.Diagnostics.Contracts;
﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace PexExamplesPermutations
{
    public class Anagrams
    {
      
        public static void Puzzle()
        {

          Contract.Assert(Anagram(wordd1,wordd2) == MyAnagram(wordd1,wordd2));

          }
      
        public static bool Anagram(string word1, string word2)
        {
            List<string> permutations = GetAllPermutations(word1);
            return permutations.Contains(word2);
        }
        
        public static bool MyAnagram(string word1, string word2)
        {  
            char[] wordd1 = word1.ToCharArray();
            char[] wordd2 = word2.ToCharArray();
            sort(wordd1, 0, wordd1.Length);
       	    sort(wordd2, 0, wordd2.Length);
       	    return Array.Equals(wordd1, wordd2);
        }

        public static List<string> GetAllPermutations(string input)
        {
            List<string> permutations = new List<string>();
            if (input.Length == 0) { 
                permutations.Add(""); 
            }
            else
            {
                permutations = GetAllPermutations(input.Substring(1,input.Length-1));
                permutations = interleave(input[0], permutations);
            }

            return permutations;
        }

        public static List<string> interleave(char elem, List<string> list)
        {
            List<string> res = new List<string>();
            foreach (string l in list) 
            {
                if (l.Length == 0)
                {
                    res.Add(elem.ToString());
                }
                else
                {
                    for (int i = 0; i <= l.Length; i++)
                    {
                        string nl = l.Substring(0, i) + elem.ToString() + l.Substring(i, l.Length - i);
                        res.Add(nl);
                    }
                }
            }
            return res;
        }


 public static void sort(char[] a)
{
    sort(a, 0, a.Length);
}

public static void sort(char[] a, int low, int high)
{
    int N = high - low;
    if (N <= 1)
        return;

    int mid = low + N / 2;

    sort(a, low, mid);
    sort(a, mid, high);

    char[] aux = new char[N];
    int i = low, j = mid;
    for (int k = 0; k < N; k++)
    {
        if (i == mid) aux[k] = a[j++];
        else if (j == high) aux[k] = a[i++];
        else if (a[j].CompareTo(a[i]) < 0) aux[k] = a[j++];
        else aux[k] = a[i++];
    }

    for (int k = 0; k < N; k++)
    {
        a[low + k] = aux[k];
    }
}       
        
    }
}
